COMMENT ⊗   VALID 00009 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\varunit 1truein
C00003 00003	\sect Introduction.
C00007 00004	\sect History.
C00013 00005	\sect Documentation for Common Lisp.
C00018 00006	\sect The Proposal.
C00022 00007	\sect Compiler.
C00025 00008	\sect Equipment.
C00027 00009	\sect Attachment.
C00030 ENDMK
C⊗;
\varunit 1truein
\input macros[can,rpg
\jpar 1000
\def\InterLisp{I{\sc NTERLISP}}
\varunit 1truein
\paper:Proposal for Common Lisp Development.1.arpa.

\sect Introduction.

Common Lisp is the combined effort of eight different Lisp implementation
groups\footnote{These groups are: Spice Lisp at CMU, DEC Common Lisp on
Vax at CMU, DEC Common Lisp on DEC-20 at Rutgers, S-1 Lisp at LLNL,
Symbolics Common Lisp, LMI Common Lisp, Portable Standard Lisp at Utah,
and Vax NIL.}  aimed at producing a common dialect of Lisp while allowing
each group to exploit its own hardware. Common Lisp is a set of documents,
a language design, and a common body of code.

The main goal of Common Lisp is to unify the experiences of the
Lisp implementations that are descended, either historically or
philosophically, from MacLisp. MacLisp is a dialect of Lisp that
emphasizes ease of system-building and efficient execution of numeric
code.  

Other goals of Common Lisp are to provide a workbench programming
language for artificial intelligence, symbolic algebra, robotics,
and education for the next decade. With such a commonly available
and commonly used Lisp it would be possible for researchers to
exchange programs with a minimum of effort, even though the two host
computers would be very different. Such a Lisp would be powerful enough
to write a sophisticated operating system sufficient to support its
own use and would, thereby, prove to be a useful systems research tool
as well as a tool for creating Lisp machine environments.

With a powerful Lisp widely available, research centers would not have
to trade off language features when deciding on what hardware to purchase.
In this way a more intelligent and effective choice could be made.

Common Lisp should support an easily-understood, portable programming style.
By making a large number of packages written in Lisp available it is hoped 
that not only would the amount of work needed to get a system running  would be
low, but the overall programming style and methodology would be improved
through exposure to expert programmers at other sites.

\sect History.

After the usefulness of the PDP-10 as a Lisp engine declined
because its address space was limited to 18 bits,  several implementation
groups started to implement Lisps for larger architectures, and these
implementations tried to improve and extend MacLisp, both to take advantage
of lessons learned from MacLisp and the various languages built on top
of it (Scheme, for example) and to also exploit the architectures the
implementors were using.

It soon became clear to several of the implementors\footnote{These
people were: Richard Gabriel of Stanford and Lawrence Livermore National
Laboratory, Guy L. Steele Jr. of Carnegie-Mellon University, Jon L. White
then of the Massachusetts Institute of Technology, and Scott Fahlman of
Carnegie-Mellon University.} that the situation of four different
Lisps \footnote{Vax NIL, SPICE Lisp, Lisp Machine Lisp, and Franz Lisp.}
all decended from MacLisp, all used by ARPA-sponsored institution, and
each different from the others in subtle, yet important ways, was intolerable
to the research community. Several key meetings among the implementors
resulted in an initial committment to unify the aproaches in the form of
a large, common subset, which was to be called `Common Lisp.' Of the four
major Lisp implementations, only Franz Lisp did not appear interested in
joining the Common Lisp group, and the reason was financial rather than
philosophical.

Since the time this informal group got together the language, Common Lisp,
has been largely designed, and a manual written that describes the
language at user-level.  The original informal group has expanded into a
larger, formal group which is collaborating on the language design and
documentation in a loose fashion. This group, called the `Common Lisp
Group', maintains a mailing list and an archive of working messages at
SAIL (Stanford Ariticial Intelligence Laboratory).

Many decisions have been made about the political organization of Common
Lisp and about what it does and does not mandate to an implementation.

If Common Lisp is to be widely used it must be available on harware not
currently supporting Common Lisp dialects. Since Common Lisp is a large
language, producing a working Common Lisp simply from the manual would
require a number of man-years. One of the next tasks to be undertaken is
to define Common Lisp in terms of a {\sl virtual machine} description.

To be useful, Common Lisp must support a large body of useful packages and
routines, so that a tradition of code, so to speak, is maintained. For example,
pattern matchers, object-oriented programming packages, and indexing routines
should be available so that projects requiring these tools can use existing,
well-tested code. In addition, these packages ought to be of certified quality of
functionality and documentation.

This description is a formal definition of a number of primitives that
must be defined on the hardware in question. Then the remainder of Common Lisp
is defined as a body of Common Lisp code written with the assumption that
these primitives exist. Once these primitives are defined on a piece of
hardware, a Common Lisp interpreter is gained by `loading' the body of
Common Lisp code.

\sect Documentation for Common Lisp.

Currently Common Lisp is nothing more than an orgranization for
documentation along with some of that docmentation. To be complete
as envisioned by the Common Lisp Group the rest of the documentation
must be brought into existence.

The Common Lisp documentation is divided into four parts, known as the
{\sl white pages}, the {\sl yellow pages}, the {\sl red pages}, 
and the {\sl blue pages}.

The {\sl white pages} is a language specification rather than an implementation
specification.  It defines a set of standard language concepts and
constructs that may be used for communication of data structures and
algorithms in the Common Lisp dialect.  This is sometimes referred to as
the ``core Common Lisp language'', because it contains conceptually
necessary or important features.  It is not necessarily implementationally
minimal.  While some features could be defined in terms of others by
writing Lisp code (and indeed may be implemented that way), it was felt
that these features should be conceptually primitive so that there might
be agreement among all users as to their usage.  (For example, bignums and
rational numbers could be implemented as Lisp code given operations on
fixnums.  However, it is important to the conceptual integrity of the
language that they be regarded by the user as primitive, and they are
useful enough to warrant a standard definition.)

The {\sl yellow pages} is a program library document, containing documentation
for assorted and relatively independent packages of code.  While the white
pages are to be relatively stable, the yellow pages are extensible; new
programs of sufficient usefulness and quality will routinely be added from
time to time.  The primary advantage of the division into white and yellow
pages is this relative stability; a package written solely in the
white-pages language should not break if changes are made to the
yellow-pages library.

The {\sl red pages} is implementation-dependent documentation; there will be one
set for each implementation.  Here are specified such
implementation-dependent parameters as word size, maximum array size,
sizes of floating-point exponents and fractions, and so on, as well as
implementation-dependent functions such as input/output primitives.

The {\sl blue pages} constitutes an implementation guide in the spirit of the
Interlisp virtual machine specification.  It specifies a subset of the
white pages that an implementor must construct, and indicates a quantity
of Lisp code written in that subset that implements the remainder of the
white pages.  In principle there could be more than one set of blue pages,
each with a companion file of Lisp code.  (For example, one might assume
{\sc IF} to be primitive and define {\sc COND} as a macro in terms of IF, while
another might do it the other way around.)

\sect The Proposal.

At present the white pages portion of Common Lisp is nearly complete, that
document being edited by Guy Steele Jr. at CMU. Since Guy Steele is
taking a leave-of-absence from CMU to work at Tartan Labs, and since Scott
Fahlman, the head of the Spice Lisp project and a major contributor to
Common Lisp, wants to return to his AI research, the administrative
control of the Common Lisp effort is in question with several important
parts left undone. Stanford proposes to complete those parts.

In particular we propose to do three things.  We will complete the white
pages: though Guy Steele will be able to work several hours a week on that
task while at Tartan Labs, it may prove impractical for him to spend all
the time needed for the job. We will help him finish the writing and
editting, arrange and direct the Common Lisp Group meetings, and perform
the administrative work necessary to complete the language specification
and documentation.

We will produce the first version of the yellow pages. This task consists
of gathering proposed packages, validating the documentation, insuring the
portability, and doing some testing of the code before it is included in
the yellow pages. All code will be uniformly housed at Stanford with
access to all ARPA contractors.  This document and library is to be
completed by the end of December 1984.

Finally, and most importantly, we will produce the first version of the
blue pages. This requires producing a detailed specification of the subset
of the white pages that must be written, expanding on the white pages
description where necessary. We will also write, test, and document an
implementation of Common Lisp in that subset and make that code available
to anyone wanting to implement a Common Lisp. Thus, for any group to
implement a Common Lisp, all that will need to be done is to write the
specified subset language in whatever other language their hardware
supports and to then take a copy of the Lisp code we will have produced
which will complete the implementation of the white pages language.
This document and code is to be completed by the end of Decemeber 1985.

\sect Compiler.

Of course, the blue pages is not complete without a portable compiler.
Such a compiler could be of the form of a machine-independent portion and
a machine-dependent portion. The machine-independent portion can perform
source-to-source transformations, flow analysis, data-structure analysis,
tail-recursion analysis, and environment analysis. The machine-dependent
portion can perform target annotation, register allocation, and code
generation. The S-1 compiler for Common Lisp is largely structured this
way. Many of the machine-dependent parts are table-driven. This compiler
could be adapted for use as a portable Common Lisp compiler.

The generation of a complete Common Lisp can be made relatively simple using
a compiler which compiles {\sl sub-primitives} such as those necessary for
doing storage allocation and performing garbage collection. The S-1 Common Lisp
system is built this way, and only about 20 pages of assembly language code
is required to build the Lisp system.

We would like to do the machine-independent compiler, but it may be impossible
to find the personnel to help with this task. Without doing the compiler
we will require a full-time staff member and a half-time graduate student.
A second full-time staff member would be required for the compiler work,
and there simply is a shortage of qualified people in the area at present.

A collaborative effort with the University of Utah could be productive
since they have considerable expertise in portable systems and have expressed
an interest in the task.

We would like to explore the issue of producing a portable compiler and
would wish to reserve the right to request additional funding for this
project if personnel are located.

\sect Equipment.

The cost of computer time to research personnel in the Computer
Science Department has risen dramatically recently. 
Not only has the cost of SAIL risen, but the feature of being able
to control the scheduler to guarantee service at a reasonable
level has been administratively removed, and the amount of
usable service available on SAIL has dropped below the tolerance
level. 

Since the work required to test the Yellow pages code and to develope the
Blue pages system require considerable computer time, the best way to
achieve the level of service needed is with a personal computer.
Therefore, we are requesting funds for one personal Lisp machine for the
computing portion of the work proposed and some funds for timesharing on
the SAIL computer for the documentation portion of the work.

\sect Attachment.

Attached to this report are several budget projections.
The first budget is for one research associate, computer time
for a timeshared system (SAIL), publications, and travel.
This budget assumes that a simple Blue pages is done---a Blue
pages without a portable compiler.

\ssect Salaries.

$$\vcenter{\halign to size{#\hfill\tabskip 0pt plus 100pt
⊗\hfill #⊗\hfill #⊗\hfill #\tabskip 0pt\cr
Item⊗1983⊗1984⊗1985\cr\noalign{\vskip 2pt\hrule\vskip 2pt}
Research Associate⊗30000⊗33000⊗36300\cr
Support⊗1000⊗1100⊗1250\cr\noalign{\vskip 2pt\hrule\vskip 2pt}
Total Salaries⊗31000⊗34100⊗37510\cr
Benefits⊗6510⊗7161⊗7877\cr}}$$

\ssect Direct Costs.

$$\vcenter{\halign to size{#\hfill\tabskip 0pt plus 100pt
⊗\hfill #⊗\hfill #⊗\hfill #\tabskip 0pt\cr
Item⊗1983⊗1984⊗1985\cr\noalign{\vskip 2pt\hrule\vskip 2pt}
Four Trips per Year⊗2000⊗2300⊗2645\cr
Expendables⊗750⊗865⊗1000\cr
Publications⊗1000⊗1100⊗1250\cr
Computer Use⊗12000⊗14400⊗17280\cr\noalign{\vskip 2pt\hrule\vskip 2pt}
Total Direct Costs⊗53260⊗59926⊗67562\cr
Indirect Costs⊗36750⊗41349⊗46618\cr\noalign{\vskip 2pt\hrule\vskip 2pt}
Total Costs⊗90009⊗101275⊗114180\cr}}$$

The second budget includes money for a graduate student. This brings the
first-year total to over $\$$100,000.  With this budget a much better
Blue pages can be done. In particular such things as the interrupt system
can be well-thought out. Still a portable compiler will not be done.

The final budget includes money for a Lisp machine and two students.
If two students are not available, a programmer could be  hired with the
money. With this budget the portable compiler will be done. This increases
the value of the Blue pages tremendously, lightening the burden on the
implementors of a Common Lisp for a new machine.

\vfill\end